kd-tree
k-dimensional tree in Rust.
Fast, simple, and easy to use.
Usage
// construct kd-tree
let kdtree = build_by_ordered_float;
// search the nearest neighbor
let found = kdtree.nearest.unwrap;
assert_eq!;
// search k-nearest neighbors
let found = kdtree.nearests;
assert_eq!;
assert_eq!;
// search points within a sphere
let found = kdtree.within_radius;
assert_eq!;
assert!;
assert!;
With or without KdPoint
KdPoint
trait represents k-dimensional point.
You can live with or without KdPoint
.
With KdPoint
explicitly
use ;
// define your own item type.
// implement `KdPoint` for your item type.
// construct kd-tree from `Vec<Item>`.
// Note: you need to use `build_by_ordered_float()` because f64 doesn't implement `Ord` trait.
let kdtree: = build_by_ordered_float;
// search nearest item from [1.9, 3.1]
assert_eq!;
With KdPoint
implicitly
KdPoint
trait is implemented for fixed-sized array of numerical types, such as [f64; 3]
or [i32, 2]
etc.
So you can build kd-trees of those types without custom implementation of KdPoint
.
let items: = vec!;
let kdtree = build;
assert_eq!;
KdPoint
trait is also implemented for tuple of a KdPoint
and an arbitrary type, like (P, T)
where P: KdPoint
.
And a type alias named KdMap<P, T>
is defined as KdTree<(P, T)>
.
So you can build a kd-tree from key-value pairs, as below:
let kdmap: KdMap = build;
assert_eq!;
nalgebra
feature
KdPoint
trait is implemented for nalgebra
's vectors and points.
Enable nalgebra
feature in your Cargo.toml:
= { = "...", = ["nalgebra"] }
Then, you can use it as follows:
use Point3;
let items: = vec!;
let kdtree = build;
let query = new;
assert_eq!;
Without KdPoint
use HashMap;
let items: = vec!.into_iter.collect;
let kdtree = build_by_key;
assert_eq!;
To own, or not to own
KdSliceN<T, N>
and KdTreeN<T, N>
are similar to str
and String
, or Path
and PathBuf
.
KdSliceN<T, N>
doesn't own its buffer, butKdTreeN<T, N>
.KdSliceN<T, N>
is notSized
, so it must be dealed in reference mannar.KdSliceN<T, N>
implementsDeref
to[T]
.KdTreeN<T, N>
implementsDeref
toKdSliceN<T, N>
.- Unlike
PathBuf
orString
, which are mutable,KdTreeN<T, N>
is immutable.
&KdSliceN<T, N>
can be constructed directly, not via KdTreeN
, as below:
let mut items: = vec!;
let kdtree = sort;
assert_eq!;
KdIndexTreeN
A KdIndexTreeN
refers a slice of items, [T]
, and contains kd-tree of indices to the items, KdTreeN<usize, N>
.
Unlike [KdSlice::sort
], [KdIndexTree::build
] doesn't sort input items.
let items = vec!;
let kdtree = build;
assert_eq!; // nearest() returns an index of found item.
Features
"serde" feature
[]
= { = "...", = ["serde"] }
You can serialize/deserialize KdTree<{serializable type}>
with this feature.
let src: = build;
let json = to_string.unwrap;
assert_eq!;
let dst: = from_str.unwrap;
assert_eq!;
"nalgebra" feature
[]
= { = "...", = ["nalgebra"] }
see above
"nalgebra-serde" feature
[]
= { = "...", = ["nalgebra-serde"] }
You can serialize/deserialize KdTree<{nalgebra type}>
with this feature.
use nalgebra as na;
let src: = build_by_ordered_float;
let json = to_string.unwrap;
assert_eq!;
let dst: = from_str.unwrap;
assert_eq!;
"rayon" feature
[]
= { = "...", = ["rayon"] }
You can build a kd-tree faster with rayon
.
let kdtree = par_build_by_ordered_float;
License
This library is distributed under the MIT License.